package org.apache.commons.graph.scc

import com.carrotsearch.junitbenchmarks.BenchmarkRule
import com.carrotsearch.junitbenchmarks.annotation.AxisRange
import com.carrotsearch.junitbenchmarks.annotation.BenchmarkMethodChart
import org.apache.commons.graph.CommonsGraph.findStronglyConnectedComponent
import org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph
import org.apache.commons.graph.GraphException
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledEdge
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.DirectedMutableGraph
import org.junit.Assert
import org.junit.BeforeClass
import org.junit.Rule
import org.junit.Test
import java.util.*

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

@AxisRange(min = 0.0, max = 2.0)
@BenchmarkMethodChart(filePrefix = "strongly-connected-components")
class SCCAlgorithmBenchmarkTestCase {
    @JvmField
    @Rule
    var benchmarkRun: BenchmarkRule = BenchmarkRule()

    @Test
    fun testPerformCheriyanMehlhornGabow() {
        val actual: Set<Set<BaseLabeledVertex>> = findStronglyConnectedComponent(graph!!).applyingCheriyanMehlhornGabow()
        Assert.assertTrue(actual.size > 0)
    }

    @Test
    fun testPerformKosaraju() {
        val actual: Set<Set<BaseLabeledVertex>> = findStronglyConnectedComponent(graph!!).applyingKosarajuSharir()
        Assert.assertTrue(actual.size > 0)
    }

    @Test
    fun testPerformTarjan() {
        val actual: Set<Set<BaseLabeledVertex>> = findStronglyConnectedComponent(graph!!).applyingTarjan()
        Assert.assertTrue(actual.size > 0)
    }

    companion object {
        private const val NODES = 5000
        private const val EDGES = 5000

        private var graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>? = null

        @JvmStatic
        @BeforeClass
        fun setUp() {
            graph = newDirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    val vertices: MutableList<BaseLabeledVertex> = ArrayList()
                    for (i in 0..<NODES) {
                        val v = BaseLabeledVertex(i.toString())
                        addVertex(v)
                        vertices.add(v)
                    }

                    val r = Random()
                    for (i in 0..<EDGES) {
                        val v1 = r.nextInt(NODES)
                        val v2 = r.nextInt(NODES)

                        try {
                            addEdge(BaseLabeledEdge(String.format("%s -> %s", v1, v2))).from(
                                vertices[v1]
                            ).to(vertices[v2])
                        } catch (e: GraphException) {
                            // ignore duplicate edge exceptions
                        }
                    }
                }
            })
        }
    }
}
